package week07

import "math"

// 1584. 连接所有点的最小费用
// https://leetcode-cn.com/problems/min-cost-to-connect-all-points/

func minCostConnectPoints(points [][]int) int {
	var dist = make([][]int, 0)
	for i := range points {
		for j := range points {
			dist = append(dist, []int{i, j, dis(points[i][0], points[i][1], points[j][0], points[j][1])})
		}
	}
	sort.Sort(EdgeSort(dist))

	var father = make([]int, len(dist))
	for i := range father {
		father[i] = i
	}

	var ans = 0
	for _, edge := range dist {
		x, y, z := edge[0], edge[1], edge[2]
		if find(father, x) == find(father, y) {
			continue
		}
		unionSet(father, x, y)
		ans += z
	}
	return ans
}

func find(father []int, x int) int {
	if father[x] != x {
		father[x] = find(father, father[x])
	}
	return father[x]
}

func unionSet(father []int, x, y int) {
	father[find(father, y)] = find(father, x)
}

type EdgeSort [][]int

func (es EdgeSort) Len() int { return len(es) }
func (es EdgeSort) Swap(i, j int) { es[i], es[j] = es[j], es[i] }
func (es EdgeSort) Less(i, j int) bool { return es[i][2] < es[j][2] }


func dis(x1, y1, x2, y2 int) int {
	return abs(x1 - x2) + abs(y1 - y2)
}

func abs(x int) int {
	if x >= 0 {
		return x
	}
	return -x
}